package lineartable.linkedlist.doublylinkedlist.doublycircularlinkedlist;

import lineartable.inter.LinearLinkedList;
import lineartable.linkedlist.doublylinkedlist.DoublyLinkedNode;

/**
 * 线性表的链式存储结构-双向循环链表
 */
public class DoublyCircularLinkedList implements LinearLinkedList {

    private DoublyLinkedNode head;

    public DoublyCircularLinkedList() {
        head = new DoublyLinkedNode();
        head.setPrior(head);
        head.setNext(head);
    }

    /**
     * 头插法建表
     *
     * @param data
     */
    @Override
    public void createListHead(char data) {

    }

    /**
     * 尾插法建表
     *
     * @param data
     */
    @Override
    public void createListTail(char data) {
        DoublyLinkedNode temp = new DoublyLinkedNode(data, head.getPrior(), head);
        head.getPrior().setNext(temp);
        head.setPrior(temp);
    }

    /**
     * 返回线性表是否为空
     *
     * @return
     */
    @Override
    public boolean listEmpty() {
        return head.getNext() == head;
    }

    /**
     * 将线性表清空
     */
    @Override
    public void clearList() {
        head.setNext(head);
        head.setPrior(head);
    }

    /**
     * 返回线性表中第i个位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public char getElem(int index) {
        DoublyLinkedNode p = head;
        for (int i = 0; i <= index; i++) {
            p = p.getNext();
        }
        return p.getData();
    }

    /**
     * 查找线性表中的元素，并返回下标
     *
     * @param e
     * @return
     */
    @Override
    public int locateElem(char e) {
        DoublyLinkedNode p = head;
        int i = 0;
        while ((p = p.getNext()) != head) {
            if (p.getData() == e) {
                return i;
            }
            i++;
        }
        return -1;
    }

    /**
     * 在线性表第i个位置插入元素e
     *
     * @param i
     * @param e
     */
    @Override
    public void listInsert(int i, char e) {
        DoublyLinkedNode p = head;
        for (int j = 0; j < i; j++) {
            p = p.getNext();
        }
        DoublyLinkedNode temp = new DoublyLinkedNode();
        temp.setData(e);
        temp.setNext(p.getNext());
        temp.setPrior(p);
        p.getNext().setPrior(temp);
        p.setNext(temp);
    }

    /**
     * 删除链表中的第i个元素
     *
     * @param i
     */
    @Override
    public void listDelete(int i) {
        DoublyLinkedNode p = head;
        for (int j = 0; j < i; j++) {
            p = p.getNext();
        }
        DoublyLinkedNode delElem = p.getNext();
        p.getNext().getNext().setPrior(p);
        p.setNext(p.getNext().getNext());
        delElem.setPrior(null);
        delElem.setNext(null);
    }

    /**
     * 返回线性表中元素个数
     *
     * @return
     */
    @Override
    public int getListLength() {
        DoublyLinkedNode p = head;
        int i = 0;
        while ((p = p.getNext()) != head) {
            i++;
        }
        return i;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");

        DoublyLinkedNode p = head;
        while ((p = p.getNext()) != head) {
            stringBuilder.append(p.getData() + ",");
        }

        if (stringBuilder.length() > 1) {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
